Error correction techniques are widely adopted as techniques for correcting errors in the bits of digital data which occurs in a system, such as a digital communication system, an information storage system or a computer system. For example, in ITU-T Recommendation G.709 (Non-Patent Literature 1) which defines the specifications of an optical transport network interface, the format of an OTUk (Optical channel Transport Unit-k) frame which is a type of optical transport frame is defined, and, in this OTUk frame, forward error correction (FEC) codes are added to a payload containing a client signal. The value “k” in OTUk is determined depending on the transmission speed, and is an integer ranging between 1 and 4. For example, in the case of data transmission using OTU1 frames, a transmission speed of approximately 2.5 Gigabit/sec per one data sequence can be secured. 1 Gigabit/sec means 1 Giga-bit per second. In the case of data transmission using OTU4 frames, a transmission speed of 100 Gigabit/sec or more per one data sequence can be secured.
Further, for an improvement in the characteristics of forward error correction, there is also provided a technique for performing interleaving on a bit sequence which is a target for error-correction coding. For example, Patent Literature 1 (Japanese Patent Application Publication No. 2011-146932) discloses an error correction encoder that includes an interleaver circuit for performing interleaving to rearrange the order of bit sequences of transmission data, an encoding circuit for applying error-correction coding to an output of the interleaver circuit, and a deinterleaver circuit for changing the order of output bit sequences in the encoding circuit to the original order existed prior to the interleaving.